package zuochengyun;


public class PaintProblem {

	//arr表示每幅画所需要的时间，num表示画匠的数量
	public int solution(int[] arr, int num){
		if(arr == null || arr.length == 0 || num < 1){
			throw new RuntimeException("err");
		}
		//sumArr[i]表示arr[0...i]的和
		int[] sumArr = new int[arr.length];
		//dp[i][j]表示i个画匠画完arr[0...j]这些画所需的最少时间
		int[][] dp = new int[num][arr.length];
		sumArr[0] = arr[0];
		dp[0][0] = arr[0];
		//对dp进行初始化
		for (int i = 1; i < sumArr.length; i++) {
			sumArr[i] = sumArr[i - 1] + arr[i];
			dp[0][i] = sumArr[i];
		}
		//dp[i][j] = min{max{dp[i - 1][k], sum[k + 1 ... j]} (0 <= k < j)};
		for (int i = 1; i < num; i++) {
			//对于i个画匠，负责j幅画，有以下方案
			//1 ~ i - 1画匠负责arr[0], 画匠i负责arr[1...j]
			//1 ~ i - 1负责arr[0...1], 画匠i负责arr[2 ... j]
			//...
			for (int j = dp[0].length; j > i - 1; j--) {
				int min = Integer.MAX_VALUE;
				for (int k = 0; k < j; k++) {
					int cur = Math.max(dp[i - 1][k], sumArr[j] - sumArr[k]);
					min = Math.min(min, cur);
				}
				dp[i][j] = min;
			}
		}
		return dp[num - 1][arr.length - 1];
	}
	
	public int solution3(int[] arr, int num){
		if(arr == null || arr.length <= 0 || num < 1){
			throw new RuntimeException("err");
		}
		//如果需要画的数目没有画匠的数目多
		if(arr.length < num){
			int max = Integer.MIN_VALUE;
			for (int i = 0; i < arr.length; i++) {
				max = Math.max(max, arr[i]);
			}
			return max;
		}else{
			int minSum = 0;
			int maxSum = 0;
			for (int i = 0; i < arr.length; i++) {
				maxSum += arr[i];
			}
			while(minSum != maxSum - 1){
				int mid = (minSum + maxSum) / 2;
				if(getNeedNum(arr, mid) > num){
					minSum = mid;
				}else{
					maxSum = mid;
				}
			}
			return maxSum;
		}
	}
	
	/**
	 * 每个画匠最多做limit的时间，画完arr中的这些画最少需要多少个工匠
	 * 这个显然就是每个画匠做最多的时间，然后所需要的画匠就最少
	 */
	public int getNeedNum(int[] arr, int limit){
		int res = 0;
		int stepSum = 0;
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] > limit){
				return Integer.MAX_VALUE;
			}
			stepSum += arr[i];
			if(stepSum > limit){
				res++;
				stepSum = arr[i];
			}
		}
		return res;
	}
}
